#include<vector>
#include<algorithm>
using namespace std;

class Solution {
    bool canPartitionKSubsets(vector<int>& groups, const vector<int>& nums, int index, int avg) {
        if (index < 0) return true;
        for (int i = 0; i < groups.size(); ++i) {
            if (groups[i] == avg) continue;
            if (groups[i] + nums[index] <= avg) {
                groups[i] += nums[index];
                if (canPartitionKSubsets(groups, nums, index - 1, avg))
                    return true;
                groups[i] -= nums[index];
            }
            if (groups[i] == 0) break;
        }
        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for (auto num : nums)
            sum += num;
        if (sum % k != 0) return false;
        int avg = sum / k;
        sort(nums.begin(), nums.end());
        if (nums.back() > avg) return false;
        int end = nums.size() - 1;
        while (end >= 0 && nums[end] == avg) {
            --k;
            --end;
        }
        vector<int>groups(k);
        return canPartitionKSubsets(groups, nums, end, avg);
    }
};

int main() {
    Solution sol;
    vector<int>nums = { 4, 3, 2, 3, 5, 2, 1 };
    sol.canPartitionKSubsets(nums, 4);
}